#include "sbrbtree.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "sbalance.h"

struct mynode {
	struct rb_node node;
	char *string;
};


struct rb_root mytree = RB_ROOT;

struct mynode * my_search(struct rb_root *root, char *string)
{
	struct rb_node *node = root->rb_node;

	while (node) {
		struct mynode *data = container_of(node, struct mynode, node);
		int result;

		result = strcmp(string, data->string);

		if (result < 0)
			node = node->rb_left;
		else if (result > 0)
			node = node->rb_right;
		else
			return data;
	}
	return NULL;
}

int my_insert(struct rb_root *root, struct mynode *data)
{
	struct rb_node **new = &(root->rb_node), *parent = NULL;

	/* Figure out where to put new node */
	while (*new) {
		struct mynode *this = container_of(*new, struct mynode, node);
		int result = strcmp(data->string, this->string);

		parent = *new;
		if (result < 0)
			new = &((*new)->rb_left);
		else if (result > 0)
			new = &((*new)->rb_right);
		else {
			new = &((*new)->rb_left);
			break;
		}

		//	return 0;
	}

	/* Add new node and rebalance tree. */
	rb_link_node(&data->node, parent, new);
	rb_insert_color(&data->node, root);

	return 1;
}

void my_free(struct mynode *node)
{
	if (node != NULL) {
		if (node->string != NULL) {
			free(node->string);
			node->string = NULL;
		}
		free(node);
		node = NULL;
	}
}

#define NUM_NODES 32
struct sb_timer_node {
	struct rb_node node;
	unsigned int timeout;	/* ms time */
};

struct rb_root sb_timer_tree = RB_ROOT;
struct sb_timer_node * sb_timer_search(struct rb_root *root, unsigned int timeout)
{
        struct rb_node *node = root->rb_node;

        while (node) {
                struct sb_timer_node *data = container_of(node, struct sb_timer_node, node);
                int result = timeout - data->timeout;

                if (result < 0)
                        node = node->rb_left;
                else if (result > 0)
                        node = node->rb_right;
                else
                        return data;
        }

        return NULL;
}

int sb_timer_insert(struct rb_root *root, struct sb_timer_node *data)
{
        struct rb_node **new = &(root->rb_node), *parent = NULL;

        /* Figure out where to put new node */
        while (*new) {
                struct sb_timer_node *this = container_of(*new, struct sb_timer_node, node);
                int result = data->timeout - this->timeout;

                parent = *new;
                if (result < 0)
                        new = &((*new)->rb_left);
                else if (result > 0)
                        new = &((*new)->rb_right);
                else {
                        new = &((*new)->rb_left);
                        break;
                }
        }

        /* Add new node and rebalance tree. */
        rb_link_node(&data->node, parent, new);
        rb_insert_color(&data->node, root);

        return 0;
}

int test()
{
	struct sb_timer_node *mn[NUM_NODES * 2 + 2];
	/* *insert */
	int i = 0;
	printf("insert node from 1 to NUM_NODES(32): \n");
	for (i = 0; i < NUM_NODES; i++) {
		mn[i] = (struct sb_timer_node *)malloc(sizeof(struct mynode));
		mn[i + NUM_NODES] = (struct sb_timer_node *)malloc(sizeof(struct mynode));
		mn[i]->timeout = i;
		mn[i + NUM_NODES]->timeout = i;
		sb_timer_insert(&sb_timer_tree, mn[i]);
		sb_timer_insert(&sb_timer_tree, mn[i + NUM_NODES]);
		printf("%d\n", i);
	}

	/* *search */
	struct rb_node *node;
	printf("search all nodes: \n");
	for (node = rb_first(&sb_timer_tree); node; node = rb_next(node))
		printf("key = %u\n", rb_entry(node, struct sb_timer_node, node)->timeout);

	/* *delete */
	printf("delete node 20: \n");
	struct sb_timer_node *data = sb_timer_search(&sb_timer_tree, 20);
	if (data) {
		rb_erase(&data->node, &sb_timer_tree);
	}

	/* *delete again*/
	printf("delete node 10: \n");
	data = sb_timer_search(&sb_timer_tree, 10);
	if (data) {
		rb_erase(&data->node, &sb_timer_tree);
	}

	/* *delete once again*/
	printf("delete node 15: \n");
	data = sb_timer_search(&sb_timer_tree, 15);
	if (data) {
		rb_erase(&data->node, &sb_timer_tree);
	}

	/* *search again*/
	printf("search again:\n");
	for (node = rb_first(&sb_timer_tree); node; node = rb_next(node))
		printf("key = %d\n", rb_entry(node, struct sb_timer_node, node)->timeout);
	return 0;
}

int test1()
{
        struct mynode *mn[NUM_NODES * 2 + 2];
        /* *insert */
        int i = 0;
        printf("insert node from 1 to NUM_NODES(32): \n");
        for (; i < NUM_NODES; i++) {
                mn[i] = (struct mynode *)malloc(sizeof(struct mynode));
                mn[i]->string = (char *)malloc(sizeof(char) * 4);
                mn[i + NUM_NODES] = (struct mynode *)malloc(sizeof(struct mynode));
                mn[i + NUM_NODES]->string = (char *)malloc(sizeof(char) * 4);
                sprintf(mn[i]->string, "%d", i);
                sprintf(mn[i+NUM_NODES]->string, "%d", i);
                my_insert(&mytree, mn[i]);
                printf("%d\n", i);
        }

        /* *search */
        struct rb_node *node;
        printf("search all nodes: \n");
        for (node = rb_first(&mytree); node; node = rb_next(node))
                printf("key = %s\n", rb_entry(node, struct mynode, node)->string);

        /* *delete */
        printf("delete node 20: \n");
        struct mynode *data = my_search(&mytree, "20");
        if (data) {
                rb_erase(&data->node, &mytree);
         //       my_free(data);
        }

        /* *delete again*/
        printf("delete node 10: \n");
        data = my_search(&mytree, "10");
        if (data) {
                rb_erase(&data->node, &mytree);
          //      my_free(data);
        }

        /* *delete once again*/
        printf("delete node 15: \n");
        data = my_search(&mytree, "15");
        if (data) {
                rb_erase(&data->node, &mytree);
           //     my_free(data);
        }

        /* *search again*/
        printf("search again:\n");
        for (node = rb_first(&mytree); node; node = rb_next(node))
                printf("key = %s\n", rb_entry(node, struct mynode, node)->string);

	printf("aaaaaaaaaaaaaaa\n");
	
	for(;;) {
		node = rb_first(&mytree); 
		if (node) {
			rb_erase(node, &mytree);
		}
		else 
			break;
	}
	printf("aaaaaaaaaaaaaaa\n");
        for (node = rb_first(&mytree); node; node = rb_next(node))
                printf("key = %s\n", rb_entry(node, struct mynode, node)->string);
	printf("aaaaaaaaaaaaaaa\n");
        return 0;
	
}

int main()
{
//	test1();
	
	FILE *file = fopen("./sb.log", "a+");
	fprintf(file, "%s", "asdf");
	return 0;
}
